﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace CSharpAlgorithm.Base
{
    /// <summary>
    /// 두 노드의 가장 가까운 동일 부모노드를 구하는 알고리즘
    /// </summary>
    class LowestCommonAncestor
    {
        List<Edge>[] G;
        int[,] parent;
        int[] depth;
        int maxCount;
        int maxLogCount;
        public LowestCommonAncestor(List<Edge>[] G, int V, int root)
        {
            this.G = G;
            this.maxCount = V + 1;
            this.maxLogCount = (int)Math.Log(V + 1, 2);
            parent = new int[maxLogCount, maxCount];
            depth = new int[maxCount];
            Dfs(root, -1, 0);
            for (int k = 0; k + 1 < maxLogCount; k++)
            {
                for (int v = 1; v <= V; v++)
                {
                    if (parent[k, v] < 0)
                    {
                        parent[k + 1, v] = -1;
                    }
                    else
                    {
                        parent[k + 1, v] = parent[k, parent[k, v]];
                    }
                }
            }
        }
        private void Dfs(int v, int p, int d)
        {
            parent[0, v] = p;
            depth[v] = d;
            for (int i = 0; i < G[v].Count; i++)
            {
                if (G[v][i].To != 0)
                {
                    Dfs(G[v][i].To, v, d + 1);
                }
            }
        }
        public int Lca(int u, int v)
        {
            if (depth[u] > depth[v])
            {
                int buf = u;
                u = v;
                v = buf;
            }
            for (int k = 0; k < maxLogCount; k++)
            {
                if (((depth[v] - depth[u]) >> k & 1) == 1)
                {
                    v = parent[k, v];
                }
            }
            if (u == v) return u;
            for (int k = maxLogCount - 1; k >= 0; k--)
            {
                if (parent[k, u] != parent[k, v])
                {
                    u = parent[k, u];
                    v = parent[k, v];
                }
            }
            return parent[0, u];
        }

    }
}
